package com.huangpeng.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author huangpeng
 * @Title 算法测试类
 * @Package
 * @Date 2021/6/28 15:22
 * @Description
 * @Version 1.0
 */
public class algorithmDifficultyTest {
    /**
     * 算法 / 数据结构：动态规划
     * 解题思路
     * 经典的背包问题。
     * 状态：dp[j] 表示是否存在一种杠铃片的选择方案使杠铃的重量达到 j
     * 初始化：dp[0] = true 如果一个杠铃片都不选，杠铃的重量就是 0
     * 转移：dp[j] = dp[j] || dp[j - weight[i]] 如果已经存在一种方案可以是杠铃的重量达到 j 或 j - weight[i]
     * 答案：dp[maxCapacity]
     *
     * 复杂度分析
     * 时间复杂度：O(n * maxCapacity)
     * 枚举每个杠铃片 O(n)，枚举每个重量 O(maxCapacity)。两者是嵌套关系，所以是O(n * maxCapacity)
     *
     * 空间复杂度：O(maxCapacity)
     * dp数组的空间耗费
     * @author hp
     */
    @org.junit.Test
    public void test1(){
        int[] weights = {1,3,5};
        int maxCapacity = 7;
        boolean[] dp = new boolean[maxCapacity + 1];
        dp[0] = true;
        int answer = 0;
        int L = weights.length;
        for (int i = 0; i < L; i++) {
            int weight = weights[i];
            for (int j = maxCapacity; j >= weight ; j--) {
                if(dp[j-weight]){
                    dp[j] = true;
                    answer = Math.max(answer,j);
                }
            }
        }
        System.out.println(answer);
    }

    /**
     * 有一排有编号的瓶子，现在你需要将这些瓶子全部拿走。
     * 你每次只可以拿走连续的若干个瓶子，并且需要保证瓶子的编号是一个“回文串”。
     * 回文串指的是正着和反着读都一样的串，例如“121”和“4664”。
     * 返回拿走所有瓶子所需要的最少次数。
     * 利用区间dp解决。
     * dp[i][j]代表从第i位到第j位最少被消除的次数。然后我们在此基础之上向外延申。
     * 对于i到j的区间，他的答案可能由i到k和k+1到j这两个区间的和，也就是dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])
     * 这只是其中一种可能性。
     * 接着我们考虑另一种。当arr[i]=arr[j]时，dp[i][j] = dp[i + 1][j - 1]
     * 意义是，若当前区间的前一个和后一个数刚好相等，那么这两个数可以直接跟随着当前区间的最后一次删除一起删除（我们无需考虑区间内部到底是做什么删除的，只要知道在最后一次删除前，这个区间剩余的和前后一定能组成新的回文子串）
     * @author hp
     */
    @org.junit.Test
    public void test2(){
        int[][] dp = new int[550][550];
        int[] arr = {1,3,4,1,5};
        int j;
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                dp[i][j] = n;
            }
        }
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int i = 0; i + 1 < n; i++) {
            if(arr[i] == arr[i + 1]){
                dp[i][i + 1] = 1;
            }else{
                dp[i][i + 1] = 2;
            }
        }
        for (int l = 2; l < n; l++) {
            for (int i = 0; i + l< n; i++) {
                j = i + l;
                if(arr[i] == arr[j]){
                    dp[i][j] = dp[i + 1][j -1];
                }
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k + 1][j]);
                }
            }
        }

        System.out.println(dp[0][n - 1]);

    }

    /**
     * 给定一个已经按绝对值升序排列的数组，找到两个数使他们加起来的和等于特定数。
     *
     * 函数应该返回这两个数的下标，index1必须小于index2。注意：数组的下标以0开始。
     *
     * 你不能对该数组进行排序。
     * 遍历nums，二分寻找数组里是否有绝对值等于target - nums的元素， 时间复杂度O（nlogn）
     *
     * 最后考虑找到目标，但正负同时在数组的情况，因为这个程序大于等于都让end = mid，所以只需要最后判断end + 1是不是目标数字即可，无需判断start-1
     * @author hp
     */
    @org.junit.Test
    public void test3(){
        int target = 1;//可变
        int[] nums = {0,-1,2,-3,4};
        List<List<Integer>> results = new ArrayList<>();
        int l = nums.length;
        for (int i = 0; i < l - 1; i++) {
            int index = checkTarget(i,nums,target - nums[i]);
            if(index != -1){
                List<Integer> list = new ArrayList<>();
                list.add(i);
                list.add(index);
                results.add(list);
            }
        }
        results.forEach(System.out::println);
    }

    public int checkTarget(int current, int[] nums, int target) {
        int l = nums.length;
        int start = current + 1;
        int end = l - 1;
        if(start > l){
            return -1;
        }
        while(start + 1 < end){
            int mid = (start + end) / 2;
            if(Math.abs(nums[mid]) >= Math.abs(target)){
                end = mid;
            }else{
                start = mid;
            }
        }
        if(nums[start] == target){
            return start;
        }else if(nums[end] == target){
            return end;
        }else if(end < (l - 1) && target == nums[end + 1]){
            return end + 1;
        }else{
            return -1;
        }
    }

    /**
     * 给您一个字符串形式的C ++文件（每行是一个字符串），我们希望您在注释行中找到“ Google”。如果注释行中有“ Google”，则返回true，否则返回false。
     * C++有两种注释方式，一种是单行注释 //，代表着//后面的本行内容均为注释，另一种是多行注释，
     * 这两者之间的部分均为注释。
     * @author hp
     */
    @org.junit.Test
    public void test4(){

    }

    /**
     * 有偶数个数相同，需要找出不同的那个数时，比如：2，3，4，4，3，5，5，6，6，7，7
     * @author hp
     */
    @org.junit.Test
    public void test5(){
    }

    /**
     * 将一个链表转换为一个数组。
     * @author hp
     */
    @org.junit.Test
    public void test6(){
    }

    /**
     * 给出两个整数 aa 和 bb , 求他们的和并以整数（int）的形式返回。
     * @author hp
     */
    @org.junit.Test
    public void test7(){
    }
}
